#include <stdio.h>
#include <stdlib.h>
#include "string.h"

char* append(char* to, char c){
	int last = strlen(to);
	to[last] = c;
	to[last + 1] = '\0';
	return to;
}

void merge(char* left, char* right, char* result){
	 int lenLeft = strlen(left);
	 int lenRight = strlen(right);
     while ( lenLeft > 0 || lenRight > 0 ){
        if (lenLeft > 0 && lenRight > 0){
			if ( left[0] <= right[0] ){
				result = append(result, left[0]);
				left++;
            }else{
 				result = append(result, right[0]);
 				right++;
            }
        }else if ( lenLeft > 0 ){
 				result = append(result, left[0]);
  				left++;
        }else if ( lenRight > 0 ){
                result = append(result, right[0]);
				right++;
        }
        lenLeft = strlen(left);
	 	lenRight = strlen(right);
    }

}    


void merge_sort(char* m , char* resultado){
	 int len = strlen(m);
    if( len <= 1 ){
        resultado[0] = m[0];
    }else{
		 int middle = (len / 2);
		 char* left;
		 left = (char*) malloc (middle+1);
		 left[0] = '\0';
		 char* right;
		 right = (char*) malloc (middle+1);
		 right[0] = '\0';
		 int x;
		 for(x = 0; x < middle; x++){
		   left[x] = m[x];
		   left[x + 1] = '\0';
		 }
		 int i;
		 int rig = 0;
 		 for( i = middle; i < len; i++ ){
			right[rig] = m[i];
			right[rig + 1] = '\0';
			rig++;
		 } 
		char resultadoLeft[strlen(left)];
		resultadoLeft[0] = '\0';
		merge_sort(left, resultadoLeft);
		free(left);
		char resultadoRight[strlen(right)];
		resultadoRight[0] = '\0';
		merge_sort(right, resultadoRight);
		free(right);
		merge(resultadoLeft, resultadoRight, resultado);
    }
}

/*
void merge_sort(char* m , char* resultado){
	 int len = strlen(m);
    if( len <= 1 ){
        resultado[0] = m[0];
    }else{
		 int middle = (len / 2);
		 char left[middle+1];
		 left[0] = '\0';
		 char right[middle+1];
		 right[0] = '\0';
		 int x;
		 for(x = 0; x < middle; x++){
		   left[x] = m[x];
		   left[x + 1] = '\0';
		 }
		 int i;
		 int rig = 0;
 		 for( i = middle; i < len; i++ ){
			right[rig] = m[i];
			right[rig + 1] = '\0';
			rig++;
		 } 
		char resultadoLeft[strlen(left)];
		resultadoLeft[0] = '\0';
		merge_sort(left, resultadoLeft);
		char resultadoRight[strlen(right)];
		resultadoRight[0] = '\0';
		merge_sort(right, resultadoRight);

		merge(resultadoLeft, resultadoRight, resultado);
    }
}*/

int main (int argc, char **argv){
	char* cadena = "hola";
	int longitud = strlen(cadena);
	char resultado[longitud];
	resultado[0] = '\0';
	
	merge_sort(cadena, resultado);
	printf("resultado: %s \n", resultado);
}
